/*
 * @(#)NearestNeighbor.java
 * 0.2 2011-12-22
 * 
 * Copyright (c) 2011 David Falk, Klaus Nicosia, Marcus Oberg.
 */

package logic;

import java.util.LinkedList;

/**
 * NearestNeighbor (greedy)-algorithm for solving TSP.
 * 
 * @author      Klaus Nicosia,
 * @author      David Falk,
 * @author      Marcus Oberg.
 */
public class NearestNeighbor {


	public static Tour getNNEuclideanTSP(Graph g, int startnode){
		return new TourArray(NNEuclideanTSP(g, startnode),g);
	}

	public static int[] NNEuclideanTSP(Graph g, int startnode) {
		int n = g.vertices.length;
		int[] tour = new int[n];
		tour[0] = 0;
		Vertex temp = g.vertices[0];
		g.vertices[0] = g.vertices[startnode];
		g.vertices[startnode] = temp;
		
		boolean[] used = new boolean[n];
		used[0] = true;
		for (int i = 1; i < n; i++) {
			int best = -1;
			for (int j = 0; j < n; j++) {
				if (!used[j] && (best == -1 || 
						g.distMatrix[tour[i-1]][j] < 
						g.distMatrix[tour[i-1]][best])) {
					best = j;
				}
			}
			tour[i] = best;
			used[best] = true;
		}
		return tour;
	}
}
